/**
*	@file QueryPreprocessor.cpp
*
*	@brief this header provides function for parsing PQL
*
*	@author li yuchen
*
*	@date 1/28/2011
*/
#include "QueryPreprocessor.h"
#include "Utility.h"
#include "PKB.h"
#include "QueryVarTable.h"
#include "QueryTNode.h"
#include "QueryTree.h"
#include "QueryOptimizer.h"
#include <fstream>
#include <iostream>
using namespace std;

/* ------------------------------------------------- type declare ---------------------------------------------- */

// the token type of each token taken from the query
static enum QueryTokenType{
	START,END,
	ADD,MINUS,MULTIPLY,
	CONSTANT,
	VARIABLE, // all text string clause         
	SEMICOLON,     
	COLON,
	DOUBLE_QUOTES,
	ROUND_BRACKET_L,
	ROUND_BRACKET_R,
	ANGLE_BRACKET_L,
	ANGLE_BRACKET_R,
	PERIOD,
	EQUAL,
	UNDERSCORE
};

// indict which part of query preprocessor detect error
static enum ErrorType{
	FILE_ERROR,
	TOKEN_ERROR,
	DECLARE_ERROR,
	SELECT_ERROR,
	QUERY_ERROR,
	SUCH_THAT_ERROR,
	WITH_ERROR,
	PATTERN_Q_ERROR,
	PATTERN_Q_VAR_ERROR,
	ENT_REF_ERROR,
	ATTR_REF_ERROR,
	EXPR_ERROR,
	END_ERROR,
	QUERY_VAR_NOT_FOUND,
	VAR_NOT_FOUND,
	QUERY_ARGUMENT_ERROR,
	STMT_NUM_OUT_OF_BOUND
};

static enum QueryParsePhase{
	DECLARE_VAR,
	SELECT_VAR,
	NORMAL_QUERY,
	PATTERN_Q_Q_QUERY
};

static bool QueryPreprocessorStop = false;

/* ------------------------------------------------- function declare ------------------------------------------- */

// clear and init for queries
static void InitQueryPreprocessor();

static void MatchDeclaration();
static void MatchSelect();
static void MatchSelectAttr();
static void MatchQuery();


// match such that query clause
static void MatchSuchThat();
//match with query clause
static void MatchWith();
// match pattern query clause
static void MatchPattern();

// handle argument for queries
static QueryArgumentValue MatchEntRef(QueryType query_type,bool is_left_arg,TNodeType& special_feed);
// handle with clause queries matching
static QueryArgumentValue MatchAttrRef(int& compare_ref);

// handle expression matching for assignment
static TNode* MatchExpr();

// insert a list of variable with the same type into query variable table
static void InsertQueryVars(TNodeType type);

// get token from query_text
static void GetToken();
// once there is incorrect query structure call this function
static void query_exit(ErrorType error_type);

// return true if the text is #
static bool IsHashSymbol(char text){return text == 35;};

/* ------------------------------------------------- variable declare ------------------------------------------- */

// hold all the query in a file
static string query_text;
// this will hold query for every token
static string query_token;
// this will indicate the token type
static QueryTokenType query_token_type = START;
// indict the current position of query preprocessor
static int query_current_position;
// indict the current clause of the query preprocessor
static int query_current_clause;

void InitQueryPreprocessor()
{
	query_text = "";
	query_token = "";
	query_token_type = START;
	query_current_position = 0;
	query_current_clause = 1;
	QueryPreprocessorStop = false;
}

void GenerateQueryTree(string information, bool read_from_file){
	//cout << information << endl;
	InitQueryPreprocessor();
	if(read_from_file){
		// get the input file stream
		ifstream input_file(information,ios::in);

		string program_line = "";

		// read the entire program in program_text
		if (input_file.is_open()){
			while(input_file.good()){
				getline(input_file,program_line);
				if(program_line.empty()) continue;
				query_text.append(" ");
				query_text.append(program_line);
			}
		}
		else {query_exit(FILE_ERROR);return;}

		// close the file
		input_file.close();
	}
	else query_text = information;


	MatchDeclaration();
	if(QueryPreprocessorStop == false) MatchSelect();
	if(QueryPreprocessorStop == false) MatchQuery();
	QueryTree::set_size(QueryTree::get_vp_query_tnodes()->size());
}

void MatchDeclaration(){
	GetToken();
	while(query_token != "Select" && !QueryPreprocessorStop){
		if(query_token == "procedure")
			InsertQueryVars(PROC_TYPE);
		else if(query_token == "assign")
			InsertQueryVars(ASSIGN_TYPE);
		else if(query_token == "call")
			InsertQueryVars(CALL_TYPE);
		else if(query_token == "while")
			InsertQueryVars(WHILE_TYPE);
		else if(query_token == "if")
			InsertQueryVars(IF_TYPE);
		else if(query_token == "stmtLst" || query_token == "stmt")
			InsertQueryVars(STMT_TYPE);
		else if(query_token == "prog"){
			GetToken();
			if(query_token == "_"){
				GetToken();
				if(query_token == "line") InsertQueryVars(STMT_TYPE);
				else {query_exit(DECLARE_ERROR); return;}
			}
			else {query_exit(DECLARE_ERROR); return;}
		}
		else if(query_token == "variable")
			InsertQueryVars(VAR_TYPE);
		else if(query_token == "constant")
			InsertQueryVars(CONST_TYPE);
		else {query_exit(DECLARE_ERROR); return;}
		if(QueryPreprocessorStop == true) return;
		GetToken();
	}
}

void InsertQueryVars(TNodeType type){
	GetToken();
	if(query_token_type != VARIABLE) { query_exit(DECLARE_ERROR);  return;}
	if(QueryVarTable::InsertQueryVar(query_token,type) == -1) { query_exit(DECLARE_ERROR); return;}

	GetToken();
	while(query_token != ";" && !QueryPreprocessorStop){
		if(query_token_type != COLON) { query_exit(DECLARE_ERROR);  return;}

		GetToken();
		if(query_token_type != VARIABLE) { query_exit(DECLARE_ERROR);  return;}
		if(QueryVarTable::InsertQueryVar(query_token,type) == -1)  { query_exit(DECLARE_ERROR); return;}

		GetToken();
	}
}

void MatchSelect(){

	QueryTNode* query_root = NULL;
	int query_var_index;
	QueryVarType query_var_type;
	GetToken();

	switch(query_token_type){
	case VARIABLE:
		if(query_token == "BOOLEAN"){ GetToken();return; }
		query_var_index = QueryVarTable::GetQueryVarIdx(query_token);
		if(query_var_index == -1) {query_exit(QUERY_VAR_NOT_FOUND);return;}
		QueryTree::get_pv_result_tuple()->push_back(query_var_index);

		query_var_type =  QueryVarTable::GetQueryVarType(query_var_index);

		switch(query_var_type){
		case PROC_TYPE:
			QueryTree::get_pv_query_var_type()->push_back(true);
			GetToken();
			if(query_token_type != PERIOD) return;
			GetToken();
			if(query_token != "procName") {query_exit(ATTR_REF_ERROR);return;}
			break;
		case VAR_TYPE:
			QueryTree::get_pv_query_var_type()->push_back(true);
			GetToken();
			if(query_token_type != PERIOD) return;
			GetToken();
			if(query_token != "varName") {query_exit(ATTR_REF_ERROR);return;}
			break;
		case CONST_TYPE:
			QueryTree::get_pv_query_var_type()->push_back(false);
			GetToken();
			if(query_token_type != PERIOD) return;
			GetToken();
			if(query_token != "value") {query_exit(ATTR_REF_ERROR);return;}
			break;
		case CALL_TYPE:
			GetToken();
			if(query_token_type != PERIOD){
				QueryTree::get_pv_query_var_type()->push_back(false);
				return;
			}
			GetToken();
			if(query_token == "stmt#"){
				QueryTree::get_pv_query_var_type()->push_back(false);
			}
			else if(query_token == "procName"){
				QueryTree::get_pv_query_var_type()->push_back(true);
			}
			else {query_exit(ATTR_REF_ERROR);return;}
			break;
		case STMT_TYPE: case ASSIGN_TYPE: case WHILE_TYPE: case IF_TYPE:
			QueryTree::get_pv_query_var_type()->push_back(false);
			GetToken();
			if(query_token_type != PERIOD) return;
			GetToken();
			if(query_token != "stmt#") {query_exit(ATTR_REF_ERROR);return;}
			break;
		default:
			{query_exit(ATTR_REF_ERROR);return;}	
		}
		break;
	// if the query is checking for a variable
	case ANGLE_BRACKET_L:
		
		MatchSelectAttr();

		while(query_token_type == COLON){
			
			MatchSelectAttr();
		}
		if(query_token_type != ANGLE_BRACKET_R) {query_exit(SELECT_ERROR);return;}
		GetToken();
		break;
	default:
		{query_exit(SELECT_ERROR);return;}
	}
}

static void MatchSelectAttr(){
	QueryArgumentValue return_value = 0;
	QueryVarType query_var_type;

	GetToken();
	if(query_token_type != VARIABLE) {query_exit(SELECT_ERROR);return;}
	return_value = QueryVarTable::GetQueryVarIdx(query_token);
	if(return_value == -1) {query_exit(QUERY_VAR_NOT_FOUND);return;}
	QueryTree::get_pv_result_tuple()->push_back(return_value);
	query_var_type = QueryVarTable::GetQueryVarType(return_value);

	
	switch(query_var_type){
	case PROC_TYPE:
		QueryTree::get_pv_query_var_type()->push_back(true);
		GetToken();
		if(query_token_type != PERIOD) return;
		GetToken();
		if(query_token != "procName") {query_exit(ATTR_REF_ERROR);return;}
		break;
	case VAR_TYPE:
		QueryTree::get_pv_query_var_type()->push_back(true);
		GetToken();
		if(query_token_type != PERIOD) return;
		GetToken();
		if(query_token != "varName") {query_exit(ATTR_REF_ERROR);return;}
		break;
	case CONST_TYPE:
		QueryTree::get_pv_query_var_type()->push_back(false);
		GetToken();
		if(query_token_type != PERIOD) return;
		GetToken();
		if(query_token != "value") {query_exit(ATTR_REF_ERROR);return;}
		break;
	case CALL_TYPE:
		GetToken();
		if(query_token_type != PERIOD){
			QueryTree::get_pv_query_var_type()->push_back(false);
			return;
		}
		GetToken();
		if(query_token == "stmt#"){
			QueryTree::get_pv_query_var_type()->push_back(false);
		}
		else if(query_token == "procName"){
			QueryTree::get_pv_query_var_type()->push_back(true);
		}
		else {query_exit(ATTR_REF_ERROR);return;}
		break;
	case STMT_TYPE: case ASSIGN_TYPE: case WHILE_TYPE: case IF_TYPE:
		QueryTree::get_pv_query_var_type()->push_back(false);
		GetToken();
		if(query_token_type != PERIOD) return;
		GetToken();
		if(query_token != "stmt#") {query_exit(ATTR_REF_ERROR);return;}
		break;
	default:
		{query_exit(ATTR_REF_ERROR);return;}	
	}
	GetToken();
}

void MatchQuery(){
	
	while(query_token_type != END){
		if(query_token == "such") MatchSuchThat();
		else if(query_token == "with") MatchWith();
		else if(query_token == "pattern") MatchPattern();
		else {query_exit(QUERY_ERROR); return;}
		if(QueryPreprocessorStop == true) return;
	}
}

// step 1: identify the query type
// step 2: match the corresponding query argument
// step 3: insert the query clause and continue the next clause
void MatchSuchThat(){
	GetToken();
	if(query_token != "that") {query_exit(SUCH_THAT_ERROR);return;}

	do{
		GetToken();
		QueryType query_type;
		QueryArgumentValue argument_a;
		QueryArgumentValue argument_b;

		// step 1:
		if(query_token == "Modifies"){
			query_type = MODIFIES;
			GetToken();
		}
		else if(query_token == "Uses"){
			query_type = USES;
			GetToken();
		}
		else if(query_token == "Calls" || query_token == "Parent" ||
			query_token == "Follows" || query_token == "Next" || query_token == "Affects" || 
			query_token == "NextBip" || query_token == "AffectsBip" ){
				string temp_token = query_token;
				GetToken();
				if(query_token_type == MULTIPLY){
					if(temp_token == "Calls") query_type = CALLS_ADV;
					else if(temp_token == "Parent") query_type = PARENT_ADV;
					else if(temp_token == "Follows") query_type = FOLLOWS_ADV;
					else if(temp_token == "Next") query_type = NEXT_ADV;
					else if(temp_token == "Affects") query_type = AFFECTS_ADV;
					else if(temp_token == "NextBip") query_type = NEXTBIP_ADV;
					else if(temp_token == "AffectsBip") query_type = AFFECTSBIP_ADV;
					GetToken();
				}
				else if(query_token_type == ROUND_BRACKET_L){
					if(temp_token == "Calls") query_type = CALLS;
					else if(temp_token == "Parent") query_type = PARENT;
					else if(temp_token == "Follows") query_type = FOLLOWS;
					else if(temp_token == "Next") query_type = NEXT;
					else if(temp_token == "Affects") query_type = AFFECTS;
					else if(temp_token == "NextBip") query_type = NEXTBIP;
					else if(temp_token == "AffectsBip") query_type = AFFECTSBIP;
				}
				else {query_exit(SUCH_THAT_ERROR);return;}
		}
		else{
			query_exit(SUCH_THAT_ERROR);
			return;
		}

		if(query_token_type != ROUND_BRACKET_L) { query_exit(SUCH_THAT_ERROR); return; }

		// step 2:
		TNodeType special_feed = OP_TYPE;
		switch(query_type){
		case MODIFIES: case USES: case CALLS: case CALLS_ADV:
			argument_a = MatchEntRef(query_type,true,special_feed);
			if(QueryPreprocessorStop == true) return;
			GetToken();
			if(query_token_type != COLON) { query_exit(SUCH_THAT_ERROR); return; }
			argument_b = MatchEntRef(query_type,false,special_feed);
			if(QueryPreprocessorStop == true) return;
			break;
		default:
			argument_a = MatchEntRef(query_type,true,special_feed);
			if(QueryPreprocessorStop == true) return;
			GetToken();
			if(query_token_type != COLON) { query_exit(SUCH_THAT_ERROR); return; }
			argument_b = MatchEntRef(query_type,false,special_feed);
			if(QueryPreprocessorStop == true) return;
			break;
		}

		GetToken();
		if(query_token_type != ROUND_BRACKET_R) { query_exit(SUCH_THAT_ERROR); return; }
		QueryTNode* new_query_tnode = QueryTree::AddQueryTNode(query_type,argument_a,argument_b);
		new_query_tnode->special_type = special_feed;
		GetToken();
		query_current_clause++;
	}while(query_token == "and");
}

void MatchWith(){
	do{
		QueryArgumentValue argument_a;
		QueryArgumentValue argument_b;
		QueryVarType query_var_type_a;
		// compare_ref:
		// 0: compare integer
		// 1: compare string
		// 2: no compare
		int compare_ref = 2;

		GetToken();
		argument_a = MatchAttrRef(compare_ref);
		if(QueryPreprocessorStop == true) return;
		query_var_type_a = QueryVarTable::GetQueryVarType(argument_a);

		GetToken();
		if(query_token_type != EQUAL) { query_exit(WITH_ERROR); return; }

		GetToken();
		switch(query_token_type){
		case CONSTANT:
			if(compare_ref == 1) { query_exit(WITH_ERROR); return; }
			argument_b = -atoi(query_token.c_str());
			break;
		case DOUBLE_QUOTES:
			GetToken();
			if(query_token_type != VARIABLE) { query_exit(WITH_ERROR); return; }
			if(compare_ref == 0) { query_exit(WITH_ERROR); return; }

			if(query_var_type_a == PROC_TYPE || query_var_type_a == CALL_TYPE) argument_b = ProcTable::GetProcIdx(query_token);
			else if(query_var_type_a == VAR_TYPE) argument_b = VarTable::GetVarIdx(query_token); 
			else { query_exit(WITH_ERROR); return; } // lefthand side of the query must be string

			if(argument_b == -1) { query_exit(VAR_NOT_FOUND); return; }
			argument_b = -argument_b;

			GetToken();
			if(query_token_type != DOUBLE_QUOTES) { query_exit(WITH_ERROR); return;}
			break;
		case VARIABLE:
			argument_b = MatchAttrRef(compare_ref);
			if(QueryPreprocessorStop == true) return;
			break;
		default:
			{ query_exit(WITH_ERROR); return;}
		}

		QueryTNode* compare_query = QueryTree::AddQueryTNode(COMPARE,argument_a,argument_b);
		if(compare_ref == 0) compare_query->special_type = STMT_TYPE;
		else if(compare_ref == 1) compare_query->special_type = PROC_TYPE;
		GetToken();
		query_current_clause++;
	}while(query_token == "and");
}

void MatchPattern(){
	do{
		QueryArgumentValue argument_a;
		QueryArgumentValue argument_b;
		QueryVarType pattern_type;
		TNode* pattern = NULL;
		bool isRelaxed = false;

		GetToken();
		if(query_token_type != VARIABLE) {query_exit(PATTERN_Q_ERROR); return; }
		argument_a = QueryVarTable::GetQueryVarIdx(query_token);
		if(argument_a == -1){ query_exit(QUERY_VAR_NOT_FOUND);return;}
		pattern_type = QueryVarTable::GetQueryVarType(argument_a);
		switch(pattern_type){
		case ASSIGN_TYPE: case IF_TYPE: case WHILE_TYPE:
			break;
		default:
			{query_exit(PATTERN_Q_ERROR);return;}
		}

		GetToken();
		if(query_token_type != ROUND_BRACKET_L) {query_exit(PATTERN_Q_ERROR);return;}

		TNodeType dummy = OP_TYPE;
		argument_b = MatchEntRef(PATTERN_Q,false,dummy);
		if(QueryPreprocessorStop == true) return;

		GetToken();
		if(query_token_type != COLON) {query_exit(PATTERN_Q_ERROR);return;}

		switch(pattern_type){
		case ASSIGN_TYPE:
			GetToken();
			if(query_token_type == UNDERSCORE){
				GetToken();
				if(query_token_type == DOUBLE_QUOTES){
					isRelaxed = true;
					pattern = MatchExpr();
					if(QueryPreprocessorStop == true) return;
					GetToken();
					if(query_token_type != UNDERSCORE) {query_exit(PATTERN_Q_ERROR);return;}
					GetToken();
				}
			}
			else if(query_token_type == DOUBLE_QUOTES){
				pattern = MatchExpr();
				if(QueryPreprocessorStop == true) return;
				GetToken();
			}
			else {query_exit(PATTERN_Q_ERROR);return;}
			break;
		case IF_TYPE:
			GetToken();
			if(query_token_type != UNDERSCORE) {query_exit(PATTERN_Q_ERROR);return;}
			GetToken();
			if(query_token_type != COLON) {query_exit(PATTERN_Q_ERROR);return;}
			GetToken();
			if(query_token_type != UNDERSCORE) {query_exit(PATTERN_Q_ERROR);return;}
			GetToken();
			break;
		case WHILE_TYPE:
			GetToken();
			if(query_token_type != UNDERSCORE) {query_exit(PATTERN_Q_ERROR);return;}
			GetToken();
			break;
		}

		if(query_token_type != ROUND_BRACKET_R) {query_exit(PATTERN_Q_ERROR);return;}
		QueryTNode* pattern_query_node = NULL;
		pattern_query_node = QueryTree::AddQueryTNode(PATTERN_Q,argument_a,argument_b);
		QueryTree::SetPattern(pattern_query_node,pattern,isRelaxed);

		GetToken();
		query_current_clause++;
	}while(query_token == "and");

}

// is_left_arg means if the matching entity is the left argument of the query
QueryArgumentValue MatchEntRef(QueryType query_type, bool is_left_arg, TNodeType& special_feed){
	QueryArgumentValue return_value = 0;
	QueryVarType query_var_type;

	GetToken();
	switch(query_token_type){
	case VARIABLE:
		return_value = QueryVarTable::GetQueryVarIdx(query_token);
		if(return_value == -1) {query_exit(QUERY_VAR_NOT_FOUND); return 0; }
		query_var_type = QueryVarTable::GetQueryVarType(return_value);

		switch(query_type){
		case CALLS: case CALLS_ADV:
			if(query_var_type != PROC_TYPE) {query_exit(ENT_REF_ERROR);return 0;}
			break;
		case MODIFIES: case USES:
			if(is_left_arg){
				if(query_var_type == CONST_TYPE || query_var_type == VAR_TYPE) 
				{query_exit(ENT_REF_ERROR);return 0;}
				if(query_var_type == PROC_TYPE){
					special_feed = PROC_TYPE;
				}else{
					special_feed = STMT_TYPE;
				}
			}
			else{
				if(query_var_type != VAR_TYPE) 
				{query_exit(ENT_REF_ERROR); return 0; }
			}
			break;
		case PATTERN_Q:
			if(query_var_type != VAR_TYPE) {query_exit(ENT_REF_ERROR);return 0;}
			break;
		default: 
		// all other query type: parent,follows,next,affects and their advance query
		// they can only have query argument from stmt,stmtlist,assign,if,while,call,progline
			if(query_var_type == CONST_TYPE || query_var_type == PROC_TYPE || query_var_type == VAR_TYPE)
			{query_exit(ENT_REF_ERROR);return 0;}
		}
		break;
	case UNDERSCORE:
		break;
	case DOUBLE_QUOTES:
		GetToken();
		if(query_token_type != VARIABLE) {query_exit(ENT_REF_ERROR);return 0;}

		switch(query_type){
		case CALLS: case CALLS_ADV:
			return_value = ProcTable::GetProcIdx(query_token);
			break;
		case MODIFIES: case USES:
			if(is_left_arg){
				return_value = ProcTable::GetProcIdx(query_token);
				special_feed = PROC_TYPE;
			}
			else return_value = VarTable::GetVarIdx(query_token);
			break;
		case PATTERN_Q:
			return_value = VarTable::GetVarIdx(query_token);
			break;
		default:
		// all other query type: parent,follows,next,affects and their advance query
		// they cannot have string reference in their argument
			{query_exit(ENT_REF_ERROR);return 0;}
		}
		if(return_value == -1) {query_exit(VAR_NOT_FOUND);return 0;}

		GetToken();
		if(query_token_type != DOUBLE_QUOTES) {query_exit(ENT_REF_ERROR);return 0;}

		// since it is a constant reference
		return_value = -return_value;
		break;
	case CONSTANT:
		switch(query_type){
		case CALLS: case CALLS_ADV: case PATTERN_Q:
			query_exit(ENT_REF_ERROR);
			return 0;
		case MODIFIES:case USES:
			if(!is_left_arg) {query_exit(ENT_REF_ERROR);return 0;}
			special_feed = STMT_TYPE;
			break;
		default:{} // all other queries can match constant
		}
		return_value =  -atoi(query_token.c_str());

		break;
	default:
		query_exit(ENT_REF_ERROR);
		return 0;
	}
	return return_value;
}

// compare_ref:
// 0: compare integer
// 1: compare string
// 2: no compare
QueryArgumentValue MatchAttrRef(int& compare_ref){
	QueryArgumentValue return_value = 0;
	QueryVarType query_var_type;

	if(query_token_type != VARIABLE) {query_exit(ATTR_REF_ERROR);return 0;}
	return_value = QueryVarTable::GetQueryVarIdx(query_token);
	if(return_value == -1) {query_exit(QUERY_VAR_NOT_FOUND);return 0;}

	query_var_type = QueryVarTable::GetQueryVarType(return_value);

	GetToken();
	if(query_token_type != PERIOD) {query_exit(ATTR_REF_ERROR);return 0;}

	GetToken();
	switch(query_var_type){
	case PROC_TYPE:
		if(query_token != "procName") {query_exit(ATTR_REF_ERROR);return 0;}
		if(compare_ref == 0) {query_exit(ATTR_REF_ERROR);return 0;}
		else if(compare_ref == 2) compare_ref = 1;
		break;
	case VAR_TYPE:
		if(query_token != "varName") {query_exit(ATTR_REF_ERROR);return 0;}
		if(compare_ref == 0) {query_exit(ATTR_REF_ERROR);return 0;}
		else if(compare_ref == 2) compare_ref = 1;
		break;
	case CONST_TYPE:
		if(query_token != "value") {query_exit(ATTR_REF_ERROR);return 0;}
		if(compare_ref == 1) {query_exit(ATTR_REF_ERROR);return 0;}
		else if(compare_ref == 2) compare_ref = 0;
		break;
	case CALL_TYPE:
		if(query_token == "stmt#"){
			if(compare_ref == 1) {query_exit(ATTR_REF_ERROR);return 0;}
			else if(compare_ref == 2){
				compare_ref = 0;
			}
		}
		else if(query_token == "procName"){
			if(compare_ref == 0) {query_exit(ATTR_REF_ERROR);return 0;}
			else if(compare_ref == 2){
				compare_ref = 1;
			}
		}
		else {query_exit(ATTR_REF_ERROR);return 0;}
		break;
	case STMT_TYPE: case ASSIGN_TYPE: case WHILE_TYPE: case IF_TYPE:
		if(query_token != "stmt#") {query_exit(ATTR_REF_ERROR);return 0;}
		if(compare_ref == 1) {query_exit(ATTR_REF_ERROR);return 0;}
		else if(compare_ref == 2) compare_ref = 0;
		break;
	default:
		{query_exit(ATTR_REF_ERROR);return 0;}	
	}
	return return_value;

}

void query_exit(ErrorType error_type){
	stringstream ss_error;
	switch(error_type){
	case FILE_ERROR:
		ss_error << "query file error!";
		break;
	case TOKEN_ERROR:
		ss_error << "query token error!";
		break;
	case DECLARE_ERROR:
		ss_error << "query declare error!";
		break;
	case SELECT_ERROR:
		ss_error << "Select clause error!";
		break;
	case QUERY_ERROR:
		ss_error << "query matching error";
		break;
	case SUCH_THAT_ERROR:
		ss_error << "query such that clause error";
		break;
	case WITH_ERROR:
		ss_error << "query with clause error";
		break;
	case PATTERN_Q_ERROR:
		ss_error << "query syntax is wrong aournd the pattern query";
		break;
	case QUERY_VAR_NOT_FOUND:
		ss_error << "variable used in the query has not been declared";
		break;
	case VAR_NOT_FOUND:
		ss_error << "variable(procedure) name used in the query has not been appeared in the source program";
		break;
	case ENT_REF_ERROR:
		ss_error << "entity reference error!";
		break;
	case EXPR_ERROR:
		ss_error << "pattern expression error";
		break;
	case ATTR_REF_ERROR:
		ss_error << "attribute compare error!";
		break;
	case PATTERN_Q_VAR_ERROR:
		ss_error << "pattern variable must be an assignment";
		break;
	case QUERY_ARGUMENT_ERROR:
		ss_error << "query has a error input type";
		break;
	case END_ERROR:
		ss_error << "query should have ended";
		break;
	case STMT_NUM_OUT_OF_BOUND:
		ss_error << "input constant reference for statement has exceed the number of statement in the program";
		break;
	}
	if(QueryPreprocessorStop == false){
		cout << ss_error.str() << endl;
		cout << "error occur at clause number: " << query_current_clause << endl;
		QueryTNode* stop_node = new QueryTNode;
		stop_node->q_type = STOP;
		stop_node->pattern = NULL;
		QueryTree::get_vp_query_tnodes()->insert(QueryTree::get_vp_query_tnodes()->begin(),stop_node);
		QueryPreprocessorStop = true;
	}
	return;
}

void GetToken(){

	// check if it is end of the file
	if(query_current_position == query_text.size()) {
		query_token_type = END;
		query_token = "";
		return;
	}

	// skip the front useless delimiter
	while(query_text.at(query_current_position) == ' ' || 
		query_text.at(query_current_position) == '\t' ||
		query_text.at(query_current_position) == '\n' ||
		query_text.at(query_current_position) == '\0' ||
		// carriage return
		query_text.at(query_current_position) == 13
		){
			// still need to check the end of file
			if(query_current_position == query_text.size() - 1) {
				query_token_type = END;
				query_token = "";
				return;
			}
			query_current_position++;
	}

	// extract the useful operators
	switch(query_text.at(query_current_position)){
	case ';':
		query_token_type = SEMICOLON;
		query_token = ";";
		query_current_position++;
		return;
	case ',':
		query_token_type = COLON;
		query_token = ",";
		query_current_position++;
		return;
	case '_':
		query_token_type = UNDERSCORE;
		query_token = "_";
		query_current_position++;
		return;
	case '+':
		query_token_type = ADD;
		query_token = "+";
		query_current_position++;
		return;
	case '-':
		query_token_type = MINUS;
		query_token = "-";
		query_current_position++;
		return;
	case '*':
		query_token_type = MULTIPLY;
		query_token = "*";
		query_current_position++;
		return;
	case '(':
		query_token_type = ROUND_BRACKET_L;
		query_token = "(";
		query_current_position++;
		return;
	case ')':
		query_token_type = ROUND_BRACKET_R;
		query_token = ")";
		query_current_position++;
		return;
	case '<':
		query_token_type = ANGLE_BRACKET_L;
		query_token = "<";
		query_current_position++;
		return;
	case '>':
		query_token_type = ANGLE_BRACKET_R;
		query_token = ">";
		query_current_position++;
		return;
	case '\"':
		query_token_type = DOUBLE_QUOTES;
		query_token = "\"";
		query_current_position++;
		return;
	case '.':
		query_token_type = PERIOD;
		query_token = ".";
		query_current_position++;
		return;
	case '=':
		query_token_type = EQUAL;
		query_token = "=";
		query_current_position++;
		return;
	default:
		if(IsDigit(query_text.at(query_current_position))) query_token_type = CONSTANT;
		else if(IsCharacter((query_text.at(query_current_position)))) query_token_type = VARIABLE;
		else { query_exit(TOKEN_ERROR); return; }
	}// end switch

	int count = 0;
	char temp;
	do{
		temp = query_text.at(count+query_current_position);
		if(query_token_type == CONSTANT){
			if(IsCharacter(temp)) { query_exit(TOKEN_ERROR); return; }
		}
		if(!IsText(temp) && !IsHashSymbol(temp)) break;
		count++;
	}while(((unsigned int)(count + query_current_position)) < query_text.size());

	query_token = query_text.substr(query_current_position,count);
	query_current_position += count;
}

TNode* MatchVar(){
	// step 1:
	int var_index = VarTable::GetVarIdx(query_token);
	if(var_index == -1) {query_exit(VAR_NOT_FOUND); return NULL;}

	// step 2:
	TNode* var_tnode = AST::CreateTNode(VAR_TYPE,var_index,NOT_APPLICABLE);
	return var_tnode;
}

TNode* MatchConstant(){
	TNode* const_tnode = AST::CreateTNode(CONST_TYPE, atoi(query_token.c_str()),NOT_APPLICABLE);
	return const_tnode;
}

TNode* MatchOp(){
	TNode* op_tnode = AST::CreateTNode(OP_TYPE,query_token.at(0),NOT_APPLICABLE);
	return op_tnode;
}

TNode* MatchExpr(){
	GetToken();
	if(query_token_type == DOUBLE_QUOTES) {query_exit(EXPR_ERROR);return NULL;}

	// stack for building up the AST
	stack<TNode*> var_stack;
	stack<TNode*> op_stack;

	// local TNode variable to build the AST
	TNode* var_current = NULL;
	TNode* cons_current = NULL;
	TNode* op_current = NULL;
	TNode* op_top = NULL;
	TNode* var1 = NULL;
	TNode* var2 = NULL;

	// phase to build the stack
	while(query_token_type != DOUBLE_QUOTES && !QueryPreprocessorStop){
		switch(query_token_type){
		case VARIABLE:
			var_current = MatchVar();
			if(QueryPreprocessorStop) return NULL;
			var_stack.push(var_current);
			GetToken();
			break;
		case CONSTANT:
			cons_current = MatchConstant();
			var_stack.push(cons_current);
			GetToken();
			break;
		case ADD:
		case MINUS:
		case MULTIPLY:
			op_current = MatchOp();
			if(op_stack.empty()){
				op_stack.push(op_current);
				GetToken();
				break;
			}
			op_top = op_stack.top();
			// the operator on the stack top which has a lower precedence
			if(GetPrecedence(op_top) < GetPrecedence(op_current)){
				op_stack.push(op_current);
				GetToken();
			}
			else{
				// pop two variable for build a substree
				if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
				var1 = var_stack.top();
				var_stack.pop();
				if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
				var2 = var_stack.top();
				var_stack.pop();
				op_stack.pop();

				// set the link in the ast
				AST::SetParent(op_top,var2);
				AST::SetSibling(var2,var1);

				// push the expression back
				var_stack.push(op_top);

				// delete the tnode for the next round for reusing the operator
				delete op_current;
			}
			break;

			// always push for (
		case ROUND_BRACKET_L:
			op_current = MatchOp();
			op_stack.push(op_current);
			GetToken();
			break;

			// case 1: operator on the top of stack is (, then match it and delete ()
			// case 2: other ususal operator, pop it and form a sub-expr and push it back to variable stack
		case ROUND_BRACKET_R:
			op_current = MatchOp();

			// bracket is not balanced
			if(op_stack.empty()) 
			{
				query_exit(EXPR_ERROR);
				return NULL;
			}

			// if it is a (, pop it for matching bracket
			op_top = op_stack.top();
			if(GetPrecedence(op_top) == 1){
				op_stack.pop();
				delete op_top;
				delete op_current;
				GetToken();
				break;
			}
			// else it is + - or *
			else{
				// pop two variable for build a substree 
				if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
				var1 = var_stack.top();
				var_stack.pop();
				if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
				var2 = var_stack.top();				 
				var_stack.pop();
				op_stack.pop();

				// set the link in the ast
				AST::SetParent(op_top,var2);
				AST::SetSibling(var2,var1);

				// push the expression back
				var_stack.push(op_top);

				// delete the tnode for the next round for reusing the operator
				delete op_current;
				break;
			}
		default:
			query_exit(EXPR_ERROR);
			return NULL;
		}
	}

	// pop all the expression and form the tree
	while(!op_stack.empty()){
		// pop two sub-exprs on the stack and pop one operator
		if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
		var1 = var_stack.top();
		var_stack.pop();
		if(var_stack.empty()) { query_exit(EXPR_ERROR); return NULL; }
		var2 = var_stack.top();				 
		var_stack.pop();
		op_top = op_stack.top();
		op_stack.pop();

		// set the link in the AST
		AST::SetParent(op_top,var2);
		AST::SetSibling(var2,var1);

		// push the expression back
		var_stack.push(op_top);
	}

	TNode* p_expr_return = var_stack.top();
	var_stack.pop();
	return p_expr_return;
}

